Дана таблица размером $$$N \times M$$$, состоящая из нулей и единиц. Вам необходимо ответить на $$$Q$$$ запросов. Каждый запрос представляет собой два целых числа $$$W$$$ и $$$H$$$. Требуется определить, существует ли в данной таблице прямоугольник, полностью состоящий из единиц, шириной ровно $$$W$$$ и высотой ровно $$$H$$$. Стороны прямоугольника должны быть параллельны сторонам таблицы.
В первой строке через пробел вводятся три целых числа: $$$N, M, Q$$$ ($$$1 \le N, M \le 10^6, N \cdot M \le 10^6, 1 \le Q \le 10^5$$$).
В следующих $$$N$$$ строках вводится сама таблица.
Каждая строка содержит $$$M$$$ символов ('0' или '1') без пробелов. В следующих $$$Q$$$ строках вводятся пары целых чисел $$$W$$$ и $$$H$$$ ($$$1 \le W \le M, 1 \le H \le N$$$).
Для каждого запроса выведите в отдельной строке "YES", если такой прямоугольник существует, и "NO" в противном случае.
3 4 2 1110 1110 0000 3 2 3 3
YES NO
4 2 3 11 10 11 11 1 4 2 1 2 2
YES YES YES